package 动态规划;

/**
 * @description: 对于一个字符串，请设计一个高效算法，计算其中最长回文子串的长度。
 * <p>
 * 给定字符串A以及它的长度n，请返回最长回文子串的长度。
 * @author: ywk
 * @date: 2020-11-03
 */
public class 最长回文子串 {
    //最长重复子串
    public static void main(String[] args) {
        System.out.println(maxStr("bbbaccc", 0, 6));
        System.out.println(maxStrState("bbbaccc"));
    }

    //3.通过动态规划
    private static String maxStrState(String s) {
        if (s.length() < 2) { // 单个字符肯定是回文串，直接返回s
            return s;
        }
        boolean[][] dp = new boolean[s.length()][s.length()];  // 初始化一个二维数组，值默认是false
        String result = s.substring(0, 1);
        for (int i = s.length() - 2; i >= 0; i--) {
            for (int j = i + 1; j < s.length(); j++) {
                dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1]);
                if (dp[i][j]) {
                    if (j - i + 1 > result.length()) {
                        result = s.substring(i, j + 1);
                    }
                }
            }
        }
        return result;
    }

    //1.通过递归
    private static String maxStr(String str, int start, int end) {
        int left = start;
        int right = end;
        String max = "";
        if (isValid(str, left, right)) {
            return str.substring(left, right + 1);
        }
        if (left < right) {
            String maxLeft = maxStr(str, start + 1, end);
            String maxRight = maxStr(str, start, end - 1);
            max = maxLeft;
            if (maxRight.length() > maxLeft.length()) {
                max = maxRight;
            }
        }
        return max;
    }
    //2.暴力破解
    private static String maxStrArr(String str) {
        String max = str.charAt(0) + "";
        for (int i = 0; i < str.length(); i++) {
            for (int j = str.length() - 1; j >= i; j--) {
                if (isValid(str, i, j)) {
                    String subStr = str.substring(i, j + 1);
                    if (subStr.length() > max.length()) {
                        max = subStr;
                    }
                }
            }
        }
        return max;
    }
    static boolean isValid(String str, int left, int right) {
        char[] array = str.toCharArray();
        while (left < right && array[left] == array[right]) {
            left++;
            right--;
        }
        return left >= right;
    }

}
